package arrays;

import java.util.Arrays;

public class Rotate {
    public static void main(String[] args){
        int[] nums={1,2,3,4,5,6,7};
        int k=3;
        rotate(nums,k);

    }
    /**
     * 3. 空间复杂度为 O(1) 的 原地:数组翻转
     */
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; ++start) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }
    }

    public static int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    /**
     * 空间复杂度为 O(1) 的 原地:数组翻转
     * @param nums
     * @param k
     */
//    public static void rotate(int[] nums, int k) {
//        reverse(nums, 0,nums.length - 1);
//        reverse(nums, 0, k-1);
//        reverse(nums, k, nums.length - 1);
//        System.out.println(Arrays.toString(nums));
//    }
//    private static void reverse(int[] nums,int start, int end){
//        int temp;
//        while(start<end){
//            temp=nums[start];
//            nums[start++]=nums[end];
//            nums[end--]=temp;
//        }
//    }
    /**
     * 1. 创建一个临时数组，长度为nums.length
     * @param nums
     * @param k
     */
//    public static void rotate(int[] nums, int k) {
//        int[] temp=new int[nums.length];
//        for(int i=0;i<nums.length;i++){
//            temp[(i+k)%nums.length]=nums[i];
//        }
//        System.out.println(Arrays.toString(temp));
//    }

}
